package com.sheng.leetcode.year2023.month04.day07;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/04/07
 * <p>
 * 1040. 移动石子直到连续 II<p>
 * <p>
 * 在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。<p>
 * 每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。<p>
 * 值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，<p>
 * 因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。<p>
 * 当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。<p>
 * 要使游戏结束，你可以执行的最小和最大移动次数分别是多少？<p>
 * 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：[7,4,9]<p>
 * 输出：[1,2]<p>
 * 解释：<p>
 * 我们可以移动一次，4 -> 8，游戏结束。<p>
 * 或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。<p>
 * <p>
 * 示例 2：<p>
 * 输入：[6,5,4,3,10]<p>
 * 输出：[2,3]<p>
 * 解释：<p>
 * 我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。<p>
 * 或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。<p>
 * 注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。<p>
 * <p>
 * 示例 3：<p>
 * 输入：[100,101,104,102,103]<p>
 * 输出：[0,0]<p>
 * <p>
 * 提示：<p>
 * 3 <= stones.length <= 10^4<p>
 * 1 <= stones[i] <= 10^9<p>
 * stones[i] 的值各不相同。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/moving-stones-until-consecutive-ii">1040. 移动石子直到连续 II</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1040 {

    @Test
    public void test01() {
//        int[] stones = {7, 4, 9};
//        int[] stones = {6, 5, 4, 3, 10};
        int[] stones = {100, 101, 104, 102, 103};
        System.out.println(Arrays.toString(new Solution().numMovesStonesII(stones)));
    }
}

class Solution {
    public int[] numMovesStonesII(int[] stones) {
        // 解读：每次移动只能移动端点石子，并且只能移动到非端点石子的位置，完成移动后的数组，要求递增或者递减
        // 先进行排序
        Arrays.sort(stones);
        int length = stones.length;
        // 双向选择
        // 如果选择最小端点作为第一次移动的端点石子，那么 stones[0] 到 stones[1] 之间的所有未占用的位置都会跳过，最多为 stones[length - 1] - stones[1] + 1 - (length - 1)
        // 如果选择最大端点作为第一次移动的端点石子，那么最多为 stones[length - 2] - stones[0] + 1 - (length - 1)
        int max = Math.max(stones[length - 1] - stones[1] + 1 - (length - 1), stones[length - 2] - stones[0] + 1 - (length - 1));
        int min = Integer.MAX_VALUE;
        // 双指针标识窗口的左右端点
        for (int i = 0, j = 0; j < length; j++) {
            // 此时需要缩小窗口，i 向右移动
            while (stones[j] - stones[i] + 1 > length) {
                i++;
            }
            // 若此时窗口内有连续的 n - 1 个石子
            if (j - i + 1 == length - 1 && stones[j] - stones[i] + 1 == length - 1) {
                min = Math.min(min, 2);
            } else {
                // 否则用 length 减去窗口内的石子数
                min = Math.min(min, length - (j - i + 1));
            }
        }
        return new int[]{min, max};
    }
}
